package algorithm.dp;

public class 不同的二叉树 {
    // 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
    //
    // 示例:
    //
    // 输入: 3
    // 输出: 5
    // 解释:
    // 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
    //
    // 1 3 3 2 1
    // \ / / / \ \
    // 3 2 1 1 3 2
    // / / \ \
    // 2 1 2 3

    public int numTrees(int n) {
        int[] gn = new int[n + 5];// gn[i] i个节点有多少个二叉树
        gn[0] = 1;
        gn[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                gn[i] += gn[j - 1] * gn[i - j];
            }
        }
        return gn[n];
    }

    public static void main(String[] args) {
        不同的二叉树 run = new 不同的二叉树();
        System.out.println(run.numTrees(10));
    }
}
